1. Technical Field
Present invention embodiments relate to hash tables, and more specifically, to improving performance of hash tables by reducing hash collisions.
2. Discussion of the Related Art
A hash table in the computer science realm is a data structure that uses a hash function to map identifying values, referred to as keys, to associated values. For example, a key can be a person's name that maps to that person's telephone number (the associated value). To accomplish this mapping, a hash table utilizes an associative array, whereby the hash function is used to transform the key into an index, called the hash, of an array element where the corresponding value is to be sought. The array element where the corresponding value is to be sought is also referred to as a slot or bucket. Each bucket can hold several items, whereby the number of buckets is typically chosen so that dividing a hash code by the number of buckets returns an acceptable distribution of “good” hashes.
Optimally, a hash function should map each possible key to a unique slot index, so as to reduce the possible of hash collisions. However, this is rarely achievable in practice, since new entries may be entered into the hash table after it is created, thereby resulting in the possibility of a hash collision due to different keys mapping to the same hash value and thus the same bucket.